package selected;

import java.util.*;

public class J0821 {
    // 1.滑动窗口的最大值
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        // 单调队列，使用pop、push、和获取队头最大值三个方法进行维护
        // 这个单调队列中存的是数组下标的索引
        Deque<Integer> dq = new LinkedList<>();

        // 先将第一个窗口加进来，因为此时不用pop，与下面的逻辑不一致
        for(int i = 0; i < k; i++){
            while(!dq.isEmpty() && nums[dq.peekLast()] <= nums[i]){
                dq.pollLast();
            }
            dq.offerLast(i);
        }
        int[] ans = new int[n - k + 1];
        // 设置当前第一个窗口的最大值
        ans[0] = nums[dq.peekFirst()];

        // 循环比较后面的值，push、pop、getMaxValue
        for(int i = k; i < n; i++){
            // push
            while(!dq.isEmpty() && nums[dq.peekLast()] <= nums[i]){
                dq.pollLast();
            }
            dq.offerLast(i);

            // pop
            while(dq.peekFirst() <= i - k){
                dq.pollFirst();
            }
            ans[i - k + 1] = nums[dq.peekFirst()];
        }
        return ans;
    }

    // 2. 最小覆盖子串
    public String minWindow(String s, String t) {
        // 滑动窗口
        char[] ss = s.toCharArray();
        char[] tt = t.toCharArray();
        int[] hash1 = new int[128];
        int[] hash2 = new int[128];
        int right = 0, left = 0, kinds = 0, count = 0;
        int minlen = Integer.MAX_VALUE, head = -1;

        // 计算子串中有效字符出现的次数及种类
        for(int i = 0; i < tt.length; i++){
            if(hash2[tt[i]]++ == 0) kinds++;
        }

        while(right < ss.length){
            // 进窗口
            char in = ss[right];
            if(++hash1[in] == hash2[in]) count++;
            while(count == kinds){
                if(right - left + 1 < minlen){
                    minlen = right - left + 1;
                    head = left;
                }
                // 出窗口
                char out = ss[left++];
                if(hash1[out]-- == hash2[out]) count--;
            }
            right++;
        }
        if(head == -1) return new String();
        else return s.substring(head, head + minlen);
    }
    // 3. 最大连续子数组的和
    public int maxSubArray(int[] nums) {
        int n = nums.length;
        if(n == 1){
            return nums[0];
        }
        int[] dp = new int[n];
        dp[0] = nums[0];
        int ret = dp[0];
        for(int i = 1; i < n; i++){
            dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]);
            ret = Math.max(ret, dp[i]);
        }
        return ret;
    }
    // 4.合并区间 （补兑）
    // 单调区间
    public int[][] merge(int[][] intervals) {
        if(intervals.length == 0){
            return new int[0][2];
        }
        // 按照左边界进行排序，这样左边界永远都是最小的
        Arrays.sort(intervals, new Comparator<int[]>(){
            public int compare(int[] interval1, int[] interval2){
                return interval1[0] - interval2[0];
            }
        });

        List<int[]> ret = new ArrayList<>();
        ret.add(intervals[0]);
        for(int i = 1; i < intervals.length; i++){
            // 开始合并区间
            if(ret.get(ret.size() - 1)[1] >= intervals[i][0]){
                // 如果上一个数组的右边届大于当前数组的左边界，进行合并
                ret.get(ret.size() - 1)[1] = Math.max(ret.get(ret.size() - 1)[1], intervals[i][1]);
            } else {
                ret.add(intervals[i]);
            }
        }
        return ret.toArray(new int[ret.size()][2]);
    }
}
